package com.fr.lintcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import org.junit.Test;

/**
*作者：furong
*日期：2016年12月28日
*时间：下午3:04:37
*/
public class Q57 {
    /**
     * @param numbers : Give an array numbers of n integer
     * @return : Find all unique triplets in the array which gives the sum of zero.
     */
	public List<List<Integer>> threeSum(int[] numbers) {
        if (numbers == null || numbers.length < 3) {
            return null;
        }
        List<List<Integer>> rs = new ArrayList<List<Integer>>();
        Set<ArrayList<Integer>> rs1 = new HashSet<ArrayList<Integer>>();
        Arrays.sort(numbers);
        int length = numbers.length;
        for (int i = 0; i < length - 2; i++) {
            for (int j = i + 1; j < length - 1; j++) {
                int k = length - 1;
                while (k > j) {
                    if (numbers[i] + numbers[j] + numbers[k] == 0) {
                        ArrayList<Integer> list = new ArrayList<Integer>();
                        list.add(numbers[i]);
                        list.add(numbers[j]);
                        list.add(numbers[k]);
                        rs1.add(list);
                        break;
                    } else if (numbers[i] + numbers[j] + numbers[k] > 0) {
                        k--;
                    } else {
                        break;
                    }
                }
            }
        }
        for (ArrayList<Integer> a : rs1) {
            rs.add(a);
        }
        return rs;
    }

    @Test
    public void testA() {
        int[] numbers = { 1, 0, -1, -1, -1, -1, 0, 1, 1, 1 };
        System.out.println(threeSum(numbers));
    }
}
